/**
 * Created with IntelliJ IDEA
 * Description:
 * User: SEKI TOMOKI
 * Date: 2023-10-03
 * Time: 20:21
 */
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode middleNode(ListNode head) {
        // if(head == null) {
        //     return head;
        // }
        // ListNode cur = head.next;
        // int length = 1;
        // while(cur != null) {
        //     length++;
        //     cur = cur.next;
        // }

        // cur = head;
        // int mid = length / 2;
        // while(mid != 0) {
        //     mid--;
        //     cur = cur.next;
        // }
        // return cur;

        if(head == null) {
            return head;
        }

        ListNode fast = head;
        ListNode slow = head;
        //偶数个节点的结束fast == null
        //奇数个节点的结束fast.next != null
        while(fast != null && fast.next != null) {
            //快指针走两步，慢指针走一步
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }
}
